package com.backpack;

public class BestTimetoBuyandSellStockII0115_122 {
//    public int maxProfit(int[] prices) {
//        //贪心：求得所有 i 与 i-1 的 正数差值，累加
//        int res = 0;
//        for (int i = 1; i < prices.length; i++) {
//            if(prices[i] > prices[i-1]) res = res + prices[i] - prices[i-1];
//        }
//        return res;
//    }

    public int maxProfit(int[] prices) {
        //动态规划思路
        //dp[i][0] 表示下标 i 天不持有该股票 手上的最大现金值为dp[i][0]
        //dp[i][1] 表示下标 i 天持有该股票 手上的最大现金值为dp[i][1]
        //返回值求： Math.max(dp[prices.length-1][0],dp[prices.length -1][1])
        int[][] dp = new int[prices.length][2];

        //初始化
        dp[0][0] = 0;
        dp[0][1] = -prices[0];

        for (int i = 1; i < prices.length; i++) {
            dp[i][0] = Math.max(dp[i-1][0],dp[i-1][1]+prices[i]);
            dp[i][1] = Math.max(dp[i-1][0]-prices[i],dp[i-1][1]);
        }
        return Math.max(dp[prices.length-1][0],dp[prices.length -1][1]);
    }
}
